//如果要以下标为i的高度构建最大的矩形，就需要找到：
    //左边第一个小于当前高度的位置left
    //右边第一个小于当前高度的位置right
    //为了快速的找到left和right，就需要用到单调栈
//维护一个高度非递减的栈
    //遍历数组时，如果发现height[i]大于top，就说明right也找到了
    //由于非递减
        //如果不考虑相邻矩形高度一致重复，所以栈下面的数一定比它上面的数小（left找到了）
        //如果相邻矩形高度一致，也可以通过right不断出栈，最终找到left
//栈内存放的是高度对应的下标，方便计算width
//为了防止出现height是一个递增序列，可以在后面插入一个0，清空栈
//考虑到数组的第二个数就比第一个数要小，为了简化代码，可以在数组的第一个位置插入0，这样一开始一定是递增的
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), ret = 0;
        stack<int> mystack;
        vector<int> newHeights(n + 2, 0);
        for (int i = 1; i < n + 1; i++)
            newHeights[i] = heights[i - 1];

        for (int i = 0; i < n + 2; i++)
        {
            while (!mystack.empty() && newHeights[mystack.top()] > newHeights[i])
            {
                int high = newHeights[mystack.top()];
                mystack.pop();
                
                int width = i - mystack.top() - 1;
                ret = max(ret, high * width);
            }

            mystack.push(i);
        }

        return ret;
    }
};